
package com.offer.leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;


/**
 * Solution46
 */
public class Solution46 {
    public static void main(String[] args) {
        Solution46 s = new Solution46();
        List<String> ret = s.permute("abc");

        for (String str : ret) {
            System.out.println(str);
        }
    }

    public final List<String> permute(String s) {

        if (s == null) {
            return Collections.EMPTY_LIST;
        }

        List<String> result = new LinkedList<>();
        boolean[] visited = new boolean[s.length()];
        Arrays.fill(visited, false);

        StringBuilder sb = new StringBuilder();
        permute(s.toCharArray(), visited, result, sb);

        return result;
    }

    private final void permute(char[] array, boolean[] visited, List<String> result, StringBuilder sb) {

        if (sb.length() == array.length) {
            result.add(sb.toString());
            return;
        }

        for (int i = 0; i < array.length; ++i) {

            if (visited[i]) {
                continue;
            }

            sb.append(array[i]);
            visited[i] = true;
            permute(array, visited, result, sb);
            sb.deleteCharAt(sb.length() - 1);
            visited[i] = false;
        }
    }

}